import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class TreeNode {
      int val;
      TreeNode left;
     TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
 }

class Solution1 {
    public TreeNode pruneTree(TreeNode root) {
        if(dfs(root)) return null;
        return root;

    }

    public boolean dfs(TreeNode root){
        if(root==null) return true;
        boolean l=dfs(root.left);
        boolean r=dfs(root.right);
        if(l) root.left=null;
        if(r) root.right=null;
        if(root.val==1) return false;


        return l&&r;

    }
}


class Solution2{
    public TreeNode pruneTree(TreeNode root) {
        if(root==null) return null;
        root.left=pruneTree(root.left);
        root.right=pruneTree(root.right);
        if(root.left==null&&root.right==null&&root.val==0) return null;
        return root;

    }


}



class Solution {
    long prev=Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;

        boolean l=isValidBST(root.left);
        if(!l) return false;
        boolean cur=false;
        if(root.val>prev) cur=true;
        prev=root.val;
        if(!cur) return false;

        boolean r=isValidBST(root.right);
        if(!r) return false;

        return true;

        boolean[] vis1= Arrays.copyOf();



    }
}


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution3 {
    int count;
    int ret=0;
    public int kthSmallest(TreeNode root, int k) {
        count=k;
        dfs(root);
        return ret;


    }
    public void dfs(TreeNode root){
        if(root==null) return;
        dfs(root.left);
        if(--count==0){
            ret=root.val;
            return;
        }
        dfs(root.right);

        StringBuffer s=new StringBuffer();

    }
}


 class Solution4 {

     List<String> list=new ArrayList();


     public List<String> binaryTreePaths(TreeNode root) {

         StringBuffer s=new StringBuffer();
         dfs(root,s);
         return list;

     }
     private void dfs(TreeNode root,StringBuffer s){
         StringBuffer s1=new StringBuffer(s);
         s1.append(Integer.toString(root.val));
         if(root.left==null&&root.right==null){
             list.add(s1.toString());
             return;
         }
         s1.append("->");

         if(root.left!=null) dfs(root.left,s1);
         if(root.right!=null) dfs(root.right,s1);

     }
 }
